The rapid growth in complexity of modem electronic circuits has forced electronic circuit designers to rely upon computer programs to assist or automate most steps of the design process. Typical circuits today contain hundreds of thousands or millions of individual pieces or “cells.” Such a design is much too large for a circuit designer or even an engineering team of designers to manage effectively manually.
One of the most difficult, complex and time-consuming tasks in the design process is known as cell placement, or, more simply, “placement.” The placement problem is the assignment of a collection of connected cells to positions in a 2-dimensional arena, such that objective functions such as total wire length, etc., are minimized.
Conventionally, both the X and Y coordinates of the cells are determined simultaneously. There are many well-known tools commercially available to accomplish this task, for example, the “Physical Compiler” commercially available from Synopsys of Mountain View, Calif.
Modern chip design methods often involve combining both large design elements with smaller design elements. For example, a large element may be a random access memory, or RAM, which may be designed by an automated memory compiler. Other examples of large design elements include intellectual property blocks, or “IP blocks.” Such IP blocks may implement complex functions, for example a processor core or a communications design, e.g., a UART, which were designed previously and made available for integration into future designs.
The smallest design element is typically a cell, which may implement a basic logic function, for example a NAND gate. Such cells may be used to integrate existing IP designs or memory blocks together, and/or to implement new designs.
It is not unusual for a large element to be three to six orders of magnitude larger than the smallest elements. For example, it is not uncommon for a RAM (random access memory) block or cell to comprise a chip area equivalent to the area of 75,000 to 100,000 individual cells.
Modern integrated circuit designs may comprise hundreds of thousands to several million individual cells that need to be placed efficiently. Even with powerful computer systems, the time required for a placement “run” may be measured in days. A successful integrated circuit design may take several such placement runs, interleaved with other design activities, for example, wiring and post-layout simulation.
The time required for a placement process is typically not linear with respect to the number of cells to be placed. For example, a typical placement process may require on the order of N1.5 time to process a design, where N is the number of cells. For example, a design of one million cells may take approximately 31 times as long to place as a design of one hundred thousand cells, an increase of only ten times the cell count.
Unfortunately, the processing requirements to place new chip designs are outpacing the rate of processing speed increases made available through advances in the computing arts. Consequently, improvements in integrated circuit design methods, especially for the placement problem, are highly sought after.